package com.dyw.Day19;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Devil
 * @create 2022-01-28-23:12
 *
 *
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 *
 * 思路: 找根节点的两个节点的关系 依次顺着 左节点的左孩子和右节点的右孩子比较
 * 左孩子的右节点和右孩子的左节点进行比较 是一个递归的思想 比较难想
 */
@SuppressWarnings("all")
public class Demo01 {

    /**
     * BFS(非递归)
     *
     * @param root
     * @return
     */
    public boolean isSymmetric01(TreeNode root){
        //当根节点为空时
        if(root==null){
            return true;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        //根节点的左右子节点都入队
        deque.add(root.left);
        deque.add(root.right);
        while(!deque.isEmpty()){
            //每两个出队
            TreeNode left = deque.poll();
            TreeNode right = deque.poll();
            //如果两个都为空 则直接跳过本次循环 因为这是满足对称情况的
            if(left==null&&right==null){
                continue;
            }
            //如果一个为空一个不为空 那么这是不对称 返回false (^是异或符号)
            if(left==null ^ left==null){
                return false;
            }
            //如果两者的值不同 也是不对称的 返回false
            if(left.val != right.val){
                return false;
            }
            //这里要记住入队的顺序，他会每两个两个的出队。
            //左子节点的左子节点和右子节点的右子节点同时
            //入队，因为他俩会同时比较。
            //左子节点的右子节点和右子节点的左子节点同时入队，
            //因为他俩会同时比较
            deque.add(left.left);
            deque.add(right.right);
            deque.add(left.right);
            deque.add(right.left);

        }
        return true;
    }

    /**
     * BFS(递归法)
     *
     * @param root
     * @return
     */
    public boolean isSymmetric02(TreeNode root) {
        //判断根节点为空的情况
        if(root==null){
            return true;
        }
        //非空的情况
        return isSymmetricHelper(root.left,root.right);
    }

    public boolean isSymmetricHelper(TreeNode left, TreeNode right){
        //若左右节点都是空 则说明该节点是叶子节点
        if(left==null&&right==null){
            return true;
        }
        //如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if(left==null||right==null||left.val!=right.val){
            return false;
        }
        //然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return isSymmetricHelper(left.left,right.right)&&isSymmetricHelper(left.right,right.left);
    }
}
